#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <fstream>
using namespace std;

int youxianji(char c)
{
    switch(c)
    {
        case'(':
        case')':
            return -1；
            break;
        
        case'+':
        case'-':
            return 0;
            break;
        case'*':
        case'/':
            return 1;
            break;     
        }
}

bool Kuohao(char c)
{
    if (c=='('||c==')')
        return true;
    else
        return false;
}

void check(char c, stack<char>& coll2, deque<char>& coll3)
{
    if(coll2.empty())
    {
        coll2.push(c);
        return;
    }
    
    if(Kuohao(c))
    {
        if(c=='(')
            coll2.push(c);
        else
        {
            while(coll2.top()!='(')
            {
                char ch = coll2.top();
                coll3.push_back(ch);
                coll2.pop();
            }

            coll2.pop();
        }
    }
    else
    {
        char sym = coll.top();
        if (youxianji(c)<=youxianji(sym))
        {
            coll2.pop();
            coll3.push_back(sym);
            check(c,coll2,coll3);
        }
        else
        {
                coll.push(c);
        }
    }
}

void allocate(deque<char>& coll1, stack<char>& coll2, deque<char>& coll3)
{
    while(!coll1.empty())
    {
        char c= coll1.front();
        coll1.pop_front();

        if(c>='0'&&c<='9')
        {
            coll3.push_back(c);
        }
        else
        {
            check(c,coll2,coll3);
        }
    }
    while(!coll2.empty())
    {
        char c = coll2.top();
        coll3.push_back(c);
        coll2.pop();
    }
}

void calculate(deque<char>& coll3, stack<int>& coll4)
{
    while(!coll3.empty())
    {
        char c = coll3.front();
        coll3.pop_front();
        if(c>='0'&&c<='9')
        {
            int op = c - '0';
            coll4.push(op);
        }
        else
        {
            int op1 = coll4.top();
            coll4.pop();
            int op2 = coll4.top();
            coll4.pop();
            swtich(c)
            {
            case '+':
                coll4.push(op2+op1)
                break;
            case '-'
                coll4.push(op2-op1)
                break;
            case '*'
                coll4.push(op2*op1)
                break;
            case '/'
                coll4.push(op2/op1)
                break;
            }
        }
    }
}

int main()
{
    deque<char> coll1;
    stack<char> coll2;
    deque<char> coll3;
    stack<char> coll4;
    string str;
    cout<<"please insert the expression, click enter to end"<<endl;
    cin>>str;
    for(int i=0;i!=str.size();++i)
    {
        coll.push_back(str[i]);
    }
    allocate(coll1,coll2,coll3);
    calculate(coll3,coll4);
    cout<<"result:"<<coll4.top()<<endl;
}